package com.algorithm.ch2.cjm.array;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

/**
 * 三数之和
 * <p>
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * <p>
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 *
 * @Author: Jie Ming Chen
 * @Date: 2018/11/12
 * @Version 1.0
 */
public class ThreeSum {

    public static void main(String[] args) {

        ThreeSum threeSum = new ThreeSum();

        int[] nums = new int[]{-4 , -2 , -1};

        List<List<Integer>> lists = threeSum.threeSum(nums);

        System.out.println(lists.toString());

    }

    public List<List<Integer>> threeSum(int[] nums) {

        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }

        this.orderByArray(nums);

        int firstRange = getPositiveIndex(nums);
        int threeRange = getNegativeIndex(nums);

        List<List<Integer>> lists = new ArrayList<>();

        int firstIndex = 0;
        while (firstIndex <= firstRange) {

            // 第一个
            int first = nums[firstIndex];

            int secondIndex = firstIndex + 1;
            while (secondIndex < nums.length - 1) {


                listList(first,secondIndex, threeRange, nums, lists);

                secondIndex++;
            }
            firstIndex++;
        }
        return lists;
    }

    /**
     * 数组排序
     *
     * @param nums
     * @return
     */
    private int[] orderByArray(int[] nums) {

        for (int i = 0; i < nums.length; i++) {

            for (int j = i + 1; j < nums.length; j++) {

                if (nums[i] < nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums;
    }

    /**
     * 非负数范围
     *
     * @param nums
     * @return
     */
    private int getPositiveIndex(int[] nums) {

        int index = -1;
        while (++index < nums.length) {

            if (nums[index] == 0) {
                return index;
            } else if (nums[index] < 0) {
                return index - 1;
            }
        }
        return -1;
    }

    /**
     * 非整数范围
     *
     * @param nums
     * @return
     */
    private int getNegativeIndex(int[] nums) {

        int index = nums.length;
        while (--index >= 0) {

            if (nums[index] == 0) {
                return index;
            } else if (nums[index] > 0) {
                return index + 1;
            }
        }
        return -1;
    }

    private void listList(int first, int secondIndex, int threeRangeIndex, int[] nums, List<List<Integer>> lists) {

        // 第二个
        int second = nums[secondIndex];
        int threeIndex = secondIndex + 1 > threeRangeIndex ? secondIndex + 1 : threeRangeIndex;

        int three = - (first + second);
        if (three > 0) {
            return ;
        }

        List<Integer> sub = null;
        for (int i = nums.length -1 ; i >= threeIndex; i--) {

            if (nums[i] > 0) {
                continue;
            }
            if (three != nums[i]) {
                continue;
            }

            sub = new ArrayList<>();
            sub.add(first);
            sub.add(second);
            sub.add(three);

            if (lists.contains(sub)) {
                continue;
            }
            lists.add(sub);
        }
    }

}
